package main

import (
	"fmt"
)

/*
将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

综上可知： 

归并排序其实要做两件事：

（1）“分解”——将序列每次折半划分。


（2）“合并”——将划分后的序列段两两合并后排序。

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如　设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8，1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11,；
*/

func main() {
	var sortArr []int
	sortArr = []int{2, 3, 4, 1, 6, 8, 9, 7, 0}
	fmt.Println(sortArr)
	MergeSort{}.Sort(sortArr)
	fmt.Println(sortArr)
	for _, v := range sortArr {
		fmt.Println(v)
	}
}

type MergeSort struct {
}

func (object MergeSort) Sort(values []int) {
	mergeSort(values)
}

func mergeSort(values []int) {
	length := len(values)
	gap := 1
	for gap < length {
		fmt.Println("  --merge by gap ", gap)
		mergebygap(values, gap)
		gap = gap * 2
		fmt.Println("    --the tuple is ", values)
	}
}

func mergebygap(values []int, gap int) {
	length := len(values)
	for i := 0; i < length; i += 2 * gap {
		mergeTwoValues(values, i, gap)
	}
}

func mergeTwoValues(values []int, start int, gap int) {

	// fmt.Println("    ---- try to merge", values[start:start+gap], "and ", values[start+gap:start+2*gap])
	length := len(values)
	if start+gap >= length {
		return
	}
	slice := make([]int, 2*gap)
	lpos, rpos, slicepos := start, start+gap, 0
	for lpos < start+gap && (rpos < start+2*gap && rpos < length) {
		if values[lpos] <= values[rpos] {
			slice[slicepos] = values[lpos]
			lpos++
		} else {
			slice[slicepos] = values[rpos]
			rpos++
		}
		slicepos++
	}
	if lpos != start+gap {
		for lpos < start+gap {
			slice[slicepos] = values[lpos]
			lpos++
			slicepos++
		}
	} else if rpos != start+2*gap && rpos != length {
		for rpos < start+2*gap && rpos < length {
			slice[slicepos] = values[rpos]
			rpos++
			slicepos++
		}
	}
	for i := 0; i < slicepos; i++ {
		values[i+start] = slice[i]
	}
	fmt.Println("    ----  merge result is ", slice[:slicepos])
	// fmt.Println("    ----  merge result is ", values[start:start+2*gap])
}
